/**
 * 
 */
package array.passed2;

/**
Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

[show hint]
Hint:
Could you do it in-place with O(1) extra space?

Related problem: Reverse Words in a String II
 */
public class RotateArray {

	
    public void rotate(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
        	return;
        }
        
        final int size = nums.length;
        final int steps = k % size;
        reverse(nums, 0, size - 1);
        reverse(nums, 0, steps - 1);
        reverse(nums, steps, size - 1);
    }
    
    private void reverse(int[] arr, int from, int to) {
    	while (from < to) {
    		int tmp = arr[from];
    		arr[from] = arr[to];
    		arr[to] = tmp;
    		from++;
    		to--;
    	}
    }
    
    private void swap(int[] arr, int i, int j) {
    	if (arr == null || arr.length == 0) {
    		return;
    	}
    	final int size = arr.length;
    	if (i < 0 || i >= size || j < 0 || j >= size || i == j) {
    		return;
    	}
    	arr[i] ^= arr[j];
    	arr[j] ^= arr[i];
    	arr[i] ^= arr[j];
    }
	
	/**
	 * 
	 */
	public RotateArray() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
